package com.wkh.datastructure.BTree;

import java.util.Arrays;

//B树
public class BTree {
    static class Node{
        int[] keys; // 关键字
        Node[] children; // 孩子
        int keyNumber; // 有效关键字数目
        boolean leaf = true; // 是否是叶子节点
        int t; // 最小度数(最小孩子数) t>=2

        public Node(int t) {
            this.t = t;
            this.children = new Node[2 * t];
            this.keys = new int[2 * t - 1];
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(keys,0,keyNumber));
        }

        //多路查找
        public Node get(int key){
            int i = 0;
            while (i<keyNumber){
                if (key == keys[i]){
                    return this;
                }
                if (key<keys[i]){
                    break;
                }
                i++;
            }
            //执行到此处，keys[i] > key 或 i == keyNumber
            //判断是否是叶子节点
            if (leaf){
                return null;
            }
            //非叶子节点的情况
            return children[i].get(key);
        }
        //向指定索引处插入key
        void insertKey(int key,int index){
            if (index>=(2 * t - 1)){
                throw new IllegalArgumentException("index:"+index+"超出索引范围");
            }
            System.arraycopy(keys,index,keys,index+1,keyNumber-index);
            keys[index] = key;
            keyNumber++;
        }
        //向children指定索引处插入child
        public void insertChild(int index,Node child){
            System.arraycopy(children,index,children,index+1,keyNumber-index);
            children[index] = child;
        }
        //删除指定索引的key
        private int removeKey(int index){
            int t = keys[index];
            System.arraycopy(keys,index+1,keys,index,keyNumber - index);
            keyNumber--;
            return t;
        }
        //移除最左边的key
        private int removeLeftMostKey(){
            return removeKey(0);
        }
        //移除最右边的key
        private int removeRightMostKey(){
            return removeKey(keyNumber-1);
        }
        //删除指定索引处的child
        Node removeChild(int index){
            Node child = children[index];
            System.arraycopy(children,index+1,children,index,keyNumber-index);
            return child;
        }
        //移除最左边的child
        Node removeLeftChildMost(){
            return removeChild(0);
        }
        //移除最右边的child
        Node removeRightChildMost(){
            return removeChild(keyNumber);
        }
        //index 孩子处左边的兄弟
        Node childLeftSibling(int index){
            return index > 0 ? children[index-1] : null;
        }
        //index 孩子处右边的兄弟
        Node childRightSibling(int index){
            return index == keyNumber ? null : children[index+1];
        }
        //赋值当前节点的所有 key 和 child 到 target
        void moveToTarget(Node target){
            int start = target.keyNumber;
            if (!this.leaf){
                //复制孩子节点
                for (int i = 0; i <= this.keyNumber; i++) {
                    target.children[start+i] = this.children[i];
                }
                //复制keys
                for (int i = 0; i < this.keyNumber; i++) {
                    target.keys[start+i] = this.keys[i];
                }
            }
        }
    }
    //根节点
    Node root;
    //树中节点的最小度数(最小的孩子节点)
    int t;
    //最大key的数目
    final int MAX_KEY_NUMBER;
    //最小key的数目
    final int MIN_KEY_NUMBER;

    public BTree() {
        //默认值为2
        this(2);
    }

    public BTree(int t) {
        this.t = t;
        root = new Node(t);
        MAX_KEY_NUMBER = 2*t-1;
        MIN_KEY_NUMBER = t-1;
    }

    //1.是否存在
    public boolean contains(int key){
        return root.get(key)!=null;
    }
    //2.新增
    public void put(int key){
        doPut(root,key,null,0);
    }

    /**
     *
     * @param node 从哪个节点开始插入
     * @param key 插入的新key
     */
    private void doPut(Node node, int key,Node parent,int index) {
        int i = 0;
        while (i<node.keyNumber){
            if (key == node.keys[i]){
                return;//更新的逻辑
            }
            //如果node.keys[i] < key 继续循环
            //如果node.keys[i] > key 退出循环 , 此时i的值就是插入位置的索引
            if (node.keys[i] > key){
                break; //此时i的值就是插入位置的索引
            }
            i++;
        }
        if (node.leaf){//叶子节点的情况
            node.insertKey(key,i);
            //存在上限
        }else{
            //非叶子节点
            /**
             * 在当前节点的第i个孩子里完成插入
             */
            doPut(node.children[i],key,node,i);
            //存在上限
        }
        //判断是否到达上限
        if (node.keyNumber == MAX_KEY_NUMBER){
            split(node,parent,index);
        }
    }

    /**
     *
     * @param left 要分裂的节点
     * @param parent 要分裂节点的父节点
     * @param index 父结点中对应的left孩子节点的索引
     */
    private void split(Node left,Node parent,int index){
        //特殊情况：分裂父节点
        if (parent == null){
            //创建新的根节点
            Node newRoot = new Node(t);
            newRoot.leaf = false;
            newRoot.insertChild(0,left);
            //做为新的根节点
            this.root = newRoot;
            parent = newRoot;
        }
        Node right = new Node(t);//新的节点
        //新结点的leaf属性与left的leaf的属性相同
        right.leaf = left.leaf;
        //数组元素的拷贝
        System.arraycopy(left.keys,t,right.keys,0,left.t-1);

        //特殊情况：分裂的节点有孩子
        if (!left.leaf){
            //拷贝孩子节点
            System.arraycopy(left.children,t,right.children,0,t);
        }
        //更改right中的有效key的数值
        right.keyNumber = t-1;
        //t-1 处的key插入到 parent 的 index 处
        int mid = left.keys[t - 1];
        parent.insertKey(mid,index);
        //更改left中的有效key的数值
        left.keyNumber = t-1;
        //right 节点作为 parent 的孩子插入到 index + 1 处
        parent.insertChild(index+1,right);
    }

    //删除
    public void remove(int key){
        doRemove(null,root,0,key);
    }

    /**
     *
     * @param parent 要删除的节点的父节点
     * @param node 要删除的节点
     * @param index 要删除的节点的索引
     * @param key 要删除的key
     */
    //删除的递归方法
    private void doRemove(Node parent,Node node,int index,int key){
        int i = 0;
        while (i<node.keyNumber){
            if (node.keys[i] >= key){
                break;
            }
            i++;
        }
        //i 有两种情况
        /**
         * ① 找到， 代表待删除key的索引
         * ② 没找到， 代表到第i个孩子继续去查找
         */
        //判断是否是叶子节点
        if (node.leaf){
            if (found(node, key, i)){
                //找到
                node.removeKey(i);
            }else{//没找到
                return;
            }
        }else{
            if (found(node, key, i)){
                //找到了
               //1.找到后继节点 -- s为后继节点
                Node s = node.children[i + 1];
                while (!s.leaf){//非叶子节点继续找s.children[0]
                    s = s.children[0];
                }
                //找到叶子节点,只要keys中索引为0的key,找到后继key
                int skey = s.keys[0];
                //2.用后继key替换待删除的key
                node.keys[i] = skey;
                //3.删除后继key
                doRemove(node,s,i+1,skey);
            }else{//没找到，到孩子节点中去查询
                doRemove(node,node.children[i],i,key);
            }
        }
        //删除后 key 数目 < 下限 (不平衡)
        if (node.keyNumber < MIN_KEY_NUMBER){
            //调整平衡
            balance(parent,node,index);
        }

    }

    /**
     *
     * @param parent 被调整的节点的父节点
     * @param x 被调整的节点
     * @param i 被调整节点的索引值
     */
    private void balance(Node parent,Node x,int i){
        //case6 根节点
        if (x == root){
            if (root.keyNumber == 0 && root.children[0] != null){
                root = root.children[0];
            }
            return;
        }
        //对应索引的左兄弟
        Node left = parent.childLeftSibling(i);
        //对应索引的右兄弟
        Node right = parent.childRightSibling(i);
        if (left != null && left.keyNumber > MIN_KEY_NUMBER){
            //case 5-1 左边富余，右旋
            //1.把父节点中的前驱key旋转下来
            x.insertKey(parent.keys[i - 1],0);
            //2.把left中最大的key旋转上去
            parent.keys[i-1] = left.removeRightMostKey();
            if (!left.leaf){
                //3.left中最大的孩子换爹
                x.insertChild(0,left.removeRightChildMost());
            }
            return;
        }
        if (right != null && right.keyNumber > MIN_KEY_NUMBER){
            //case 5-2 右边富余，左旋
            //1.父节点中后缀key旋转下来
            x.insertKey(parent.keys[i],x.keyNumber);
            //2.right中最小的孩子换爹
            if (!right.leaf){
                x.insertChild(x.keyNumber+1,right.removeLeftChildMost());
            }
            //3.right中最小的key旋转上去
            parent.keys[i] = right.removeLeftMostKey();
            return;
        }
        //case 5-3 两边都不够借，向左合并
        if (left != null){
            //向左兄弟合并
            //1.从父节点中移除当前被调整的节点
            parent.removeChild(i);
            //2.从父节点中移除i-1位置的key
            int key = parent.removeKey(i - 1);
            //3.把移除的key添加到左边节点
            left.insertKey(key,left.keyNumber);
            //4.复制当前被调整节点到左边节点
            x.moveToTarget(left);
        }else{
            //没有左兄弟，向自己合并
            //1.从父节点中移除当前被调整节点的右兄弟
            parent.removeChild(i+1);
            //2.从父节点中移除i位置的key
            int key = parent.removeKey(i - 1);
            //3.把移除的key添加到左边节点
            x.insertKey(key,x.keyNumber);
            //4.复制当前被调整节点的右节点到当前被调整节点
            right.moveToTarget(x);
        }
    }
    /**
     * ① 找到， 代表待删除key的索引
     * ② 没找到， 代表到第i个孩子继续去查找
     */
    private boolean found(Node node, int key, int i) {
        return i < node.keyNumber && key == node.keys[i];
    }
}
